package ink.lovejinhu.leetcode;

import ink.lovejinhu.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author jinhu
 * created 2021-07-09 9:15
 */
public class Solution_0235 {
    List<List<TreeNode>> lists=new ArrayList<>();

    /**
     * 最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        this.findWay(root, p, q, new ArrayList<TreeNode>());
        for (List<TreeNode> var1 : lists
        ) {
            for (TreeNode temp :
                    var1) {
                System.out.print(temp.val + "->");
            }
            System.out.println();
        }
        return null;

    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(4);
        TreeNode treeNode4 = new TreeNode(5);
        TreeNode treeNode5 = new TreeNode(6);
        TreeNode treeNode6 = new TreeNode(7);
        TreeNode treeNode7 = new TreeNode(8);
        TreeNode treeNode8 = new TreeNode(9);
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        treeNode1.left = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode4.left = treeNode6;
        treeNode4.right = treeNode7;
        treeNode7.right = treeNode8;
        new Solution_0235().lowestCommonAncestor(treeNode, treeNode6, treeNode3);
    }

    public List<TreeNode> findWay(TreeNode root, TreeNode p, TreeNode q, List<TreeNode> way) {
        if (root == null) {
            lists.add(way);
            return way;
        }
        if (root == p) {
            way.add(p);
            lists.add(way);
            return way;
        } else if (root == q) {
            way.add(q);
            lists.add(way);
            return way;
        } else {
            way.add(root);
            lists.add(findWay(root.left, p, q, way));
            lists.add(findWay(root.right, p, q, way));
        }
        return null;
    }

}
